package main.java.indi.zyj.sword;

import java.util.Arrays;

public class InventoryManagement3 {

    public int[] inventoryManagement(int[] stock, int cnt) {

        quickSort(stock, 0, stock.length - 1);

        return Arrays.copyOf(stock, cnt);

    }



    public void quickSort(int[] stock, int low, int high) {

        if (low < high) {
            int mid = getMid(stock, low, high);
            quickSort(stock, low, mid - 1);
            quickSort(stock, mid + 1, high);
        }

    }

    private int getMid(int[] stock, int low, int high) {

        int temp = stock[low];
        while (low < high) {
            while (low < high && stock[high] >= temp) high--;
            stock[low] = stock[high];
            while (low < high && stock[low] <= temp) low++;
            stock[high] = stock[low];
        }
        stock[low] = temp;
        return low;
    }

    private void heapSort(int[] a, int n) {
        buildMaxHeap(a, n);
        for (int i = n - 1; i >= 0; i--) {
            swap(a, i, 0);
            adjust(a, i, n);
        }
    }

    private void buildMaxHeap (int[] a, int n) {
        int lastNodeIndex = n - 1;
        int lastParentNodeIndex = (lastNodeIndex - 1) / 2;
        for (int i = lastParentNodeIndex; i >= 0; i--) {
            adjust(a, i, n);
        }
    }

    private void adjust(int[] a, int i, int n) {
        int max = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && a[left] > a[max]) {
            max = left;
        }
        if (right < n && a[right] > a[max]) {
            max = right;
        }
        if (i != max) {
            swap(a, i, max);
            adjust(a, max, n);
        }
    }


    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }


}
